Batch 2 - Class 54 - Logic - Induction
Preclass Exercise:
- A real puzzle with truth tables - Bob, Ted,and Carol play a hat game. This particular game is played with 5 hats, three red, and two blue. Each person gets one hat put on his or her head. Bob can see Ted’s hat and Carol’s hat but can’t see his own. Ted can see Bob’s hat and Carol’s hat, but not his own. Carol cannot see any of the hats. The game is to see which player is the first to figure out what color hat he or she is wearing. Bob goes first. He says he can’t tell. Then Ted says he can’t tell. Carol now says she is wearing a red hat. How did she know?
HTML Content
- Draw the equivalent of truth table for this (instead of T and F, it will be color of hats - first draw all possibilities, then start to reduce possibilities)
- "Constraining the truth table" can provide answers
- Answer: Notice that in the final analysis, all four possibilities have Carol wearing the Red Hat
Bob Ted Carol <2 Blue Hats? Bob Doesn't Know? Ted Doesn't Know? Carol's Hat? R R R T T T R B R R T T T R R B R T T T R R R B T T F B B R T T T R B R B T T F R B B T F B B B F
Attendance: Tishyaa, Smiti, Muskaan, Aryan, Shubham, Anisha, Kushaan, Abhiram, Praharsh, Nandini, Rhea
Class Notes:
- (MC - 9 - 1) One square was cut from a 16x16 sqaure grid. Prove that the figure obtained can be dissected into trominos (3 squares in corner shape).
Instructor Notes: Let students think and about the problem, and come up with some answers. Note that simple divisibility by 3 doesn't suffice. After a bit, ask them to solve the problem for a 2x2 square. Once that is done, as them to do it for 4x4. They might do it by taking three possible cases. Guide them towards thinking about a 4x4 square as composition of 2x2 squares. Then 8x8 - by now the pattern must get intuitive.
- What can we say about any square?
- Careful: We have just said something about powers of 2, not an arbitrary square!
- Visualization
- How can we generalize the statement?
- Take the dominos analogy - to illustrate that the first domino requires a push (i.e. base case), and then every domino will fall if the previous one falls (i.e. induction step)
Introduce notion of variable. And then formalize the proof of this problem. (If 2^nx2^n square missing a square can be cut into trominos, then so can a 2^(n+1)x2^(n+1) square missing a square)
Introduce the terminology - Induction, Induction Hypothesis, Base, and Induction Step
- (Decade - 6 - 2.2) Another simple example: Upon being defeated and forced to abandon his castle forever, an evil magician casts a spell: if it rains one day over the castle, then it will rain the next day too. It happens to rain there today. What can we say about the future?Answer: It will rain forever. Get kids to identify the hypothesis, base and induction steps
- (Decade - 6 - 3.1) Prove that sum of first n odd natural numbers is n^2Instructor Notes: Clarify that the above statement is the induction hypothesisWhat should be the basis? Is that provable?What should be the induction step? Can you prove that step?
- (MC - 9 - 6) Into how many regions do n lines divide the plane, given that none of them are parallel, and not more than two intersect at a point.Kids will first have to form the hypothesis. Ask them to solve for a few cases to develop the hypothesisNow, ask them to prove the hypothesis using induction
Homework:
(MartinShCol - 13.21)
References:
Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg
A Decade of the Berkeley Math Circle. The American Experience, Volume 1. Zvezdelina Stankova, Tom Rike
The Colossal Book of Short Puzzles and Problems, by Martin Gardner